#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;
//找字符串中所有异位词
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int ssize = s.size();
        int psize = p.size();
        std::vector<int> ret;
        std::unordered_map<char, int> hashp;
        for (auto ch : p) {
            hashp[ch]++;
        }
        std::unordered_map<char, int> hash;
        for (int i = 0; i < psize; i++)
        {
            hash[s[i]]++;
        }
        if (hash == hashp)
            ret.push_back(0);
        for (int left = 0, right = psize - 1; right < ssize;) {
            hash[s[++right]]++;
            hash[s[left++]]--;
            if (hash[s[left - 1]] == 0)
                hash.erase(s[left - 1]);
            if (hash == hashp)
                ret.push_back(left);
        }
        return ret;
    }
};
int main()
{
    Solution s1;
    string s = "cbaebabacd", p = "abc";
    vector<int> v(s1.findAnagrams(s, p));
    for (auto ch : v)
    {
        cout << ch << " ";
    }
    cout << endl;
	return 0;
}